package com.chj.jz.dp.class04;

//https://www.lintcode.com/problem/palindrome-partitioning-ii/description
public class Code02_PalindromePermutationII {
	public static boolean[][] calcPalin(char[] s) {
		int n = s.length;
		boolean[][] f = new boolean[n][n];
		int i, j, c;
		for (i = 0; i < n; i++) {
			for (j = 0; j < n; j++) {
				f[i][j] = false;
			}
		}

		for (c = 0; c < n; c++) {
			i = c;
			j = c;
			while (i >= 0 && j < n && s[i] == s[j]) {
				f[i][j] = true;
				i--;
				j++;
			}
		}

		for (c = 0; c < n - 1; c++) {
			i = c;
			j = c + 1;
			while (i >= 0 && j < n && s[i] == s[j]) {
				f[i][j] = true;
				i--;
				j++;
			}
		}

		return f;
	}

	public static int minCut(String ss) {
		char[] s = ss.toCharArray();
		int n = s.length;

		if (n == 0) {
			return 0;
		}

		boolean[][] isPalin = calcPalin(s);
		int i, j;
		int[] f = new int[n + 1];
		f[0] = 0;

		for (i = 1; i <= n; i++) {
			f[i] = Integer.MAX_VALUE;
			for (j = 0; j < i; j++) {
				if (isPalin[j][i - 1]) {
					f[i] = Math.min(f[i], f[j] + 1);
				}
			}
		}

		return f[n] - 1;
	}

	public static void main(String[] args) {
		{
			System.out.println(minCut("a"));
		}
		{
			System.out.println(minCut("aab"));
		}
	}
}
